KKT_1D_GTV

This repo implements the algorithm in the paper A unified approach for a 1D generalized total variation problem. Mathematical Programming, February, 2021.

The problem to be solved is of the form:

Both and functions are arbitrary convex functions.

Special cases

Below are some special cases of 1D-GTV that are implemented in the code:

L2-TV

Sample run on data generated according to [1] (non-weighted):

Problem scale (n)	10	100	1000	10000	100000	1000000	10000000
Average runtime (ms)	0	0	2	8.4	60.6	2647.4	8952.8
Runtime std (ms)	0	0	0	0.8	3.07246	93.8266	278.203

[1] Condat, L.: A direct algorithm for 1-D total variation denoising. IEEE Signal Process. Lett. 20(11), 1054--1057 (2013).

Sample run on data generated according to [2] (weighted):

Problem scale (n)	10	100	1000	10000	100000	1000000	10000000
Average runtime (ms)	0	0	0	3	28	271.6	2718
Runtime std (ms)	0	0	0	0	1.26491	11.6722	30.9839

[2] Barbero, Á., Sra, S.: Modular proximal optimization for multidimensional total-variation regularization. J. Mach. Learn. Res. 19(1), 2232--2313 (2018).

piecewise-quadratic-TV

Each is a convex piecewise quadratic function.

Sample run times for increasing n:

Problem scale (n)	10	100	1000	10000	100000	1000000
Average runtime (ms)	0	0	2	18.6	198.4	2094
Runtime std (ms)	0	0	0	1.0198	6.97424	40.5364

Sample run times for increasing number of breakpoints per :

#breakpoints	100	200	300	400	500	600
Average runtime (ms)	198.2	241.2	279	290.8	300	313.4
Runtime std (ms)	1.16619	11.0164	7.79744	5.49181	8.50882	6.74092
n is fixed to 100000.

L2-Tikhonov

Sample run times:

Problem scale (n)	10	100	1000	10000	100000	1000000	10000000
Average runtime (ms)	0	0	1	15.2	160.8	1550.6	15403.2
Runtime std (ms)	0	0	0	1.16619	9.36803	39.0056	175.991

L1-TV

Sample run times:

Problem scale (n)	10	100	1000	10000	100000	1000000	10000000
Average runtime (ms)	0	0	0	4.2	54.2	497.2	4928.6
Runtime std (ms)	0	0	0	0.4	3.18748	9.08625	174.691

piecewise-linear-TV

Each is a convex piecewise linear function.

Sample run times for increasing n:

Problem scale (n)	10	100	1000	10000	100000	1000000
Average runtime (ms)	0	0	1	17	177	1772.6
Runtime std (ms)	0	0	0	0	2.44949	37.4945

Sample run times for increasing number of breakpoints per :

#breakpoints	100	200	300	400	500	600
Average runtime (ms)	171.6	226.8	255.6	271.8	282.4	296
Runtime std (ms)	1.35647	3.81576	1.49666	2.92575	2.41661	1.89737
n is fixed to 100000.

Lp-Lq

Sample run times of p = q = 4:

Problem scale (n)	10	100	1000	10000	100000	1000000	10000000
Average runtime (ms)	0	0	2	21.4	213.4	1997	20344.4
Runtime std (ms)	0	0	0	0.489898	18.4781	18.868	396.665

Huber-TV

Each is a Huber loss function defined as:

Sample run times:

Problem scale (n)	10	100	1000	10000	100000	1000000	10000000
Average runtime (ms)	0	0	0	3.6	45.8	435.2	4077.8
Runtime std (ms)	0	0	0	0.489898	1.16619	27.0215	60.562

L2-Huber

Sample run times:

Problem scale (n)	10	100	1000	10000	100000	1000000	10000000
Average runtime (ms)	0	0	0	8.4	81.4	826.8	8143.4
Runtime std (ms)	0	0	0	0.8	3.38231	10.1863	137.283

Linear-L2 (Laplacian on a path)

Sample run times:

Problem scale (n)	10	100	1000	10000	100000	1000000	10000000
Average runtime (ms)	0	0	0	0	0	1.4	17.2
Runtime std (ms)	0	0	0	0	0	0.8	9.92774

For all the above experimental results:

• Each average is taken by 5 runs of randomly (if not specified) generated data and coefficients.
• All runs are on a MacBook (Big Sur) of 2.4 GHz 8-Core Intel Core i9, 32 GB 2667 MHz DDR4 memory.

Run prebuilt executable

For a sample run of all special case problems implemented:

cd bin
./run.sh

It will output runtime profiles in the /tmp/ folder.

To see the full runtime arguments,

cd bin
./kkt_main

Build from the source

This project is a cmake project. To build from the source:

mkdir build && cd build
cmake .. && make -j5

Solve your own problem

To solve (1D-GTV) problem of your own and functions, simply update the functions compDrvt(...) and compSepInv(...) in kkt.hpp to compute the derivatives and the inverses of derivatives for your and functions respectively.

Reference

Please cite the paper if you use the algorithm.

Lu, C., Hochbaum, D.S. A unified approach for a 1D generalized total variation problem. Math. Program. (2021). https://doi.org/10.1007/s10107-021-01633-2